\label{chap:tests}
\section{Format of tests.}
Individual tests are prepared in form of input files for \emph{circuit-basis} program. Each file contains a description of digraph in form o adjacency matrix. Digraphs are designed both for covering program boundary conditions as well as the correctness of implemented algorithms. Test files follow naming convention of \emph{\(<\)graph name\(>\)\(<\)number of vertices\(>\).in}. 

Test validation can be done by running the program with option \emph{-d} which colors base circuits red. In a \emph{strongly connected} graph only bidirectional edges, forming a \emph{subtree} with one vertice in common with the rest of the graph, will remain blue (they are not part of any circuit so are not contained in the base).

\section{Test files listing and description.}

\subsection{\emph{full4.in}}
This test file contains a digraph in which any pair of vertices is connected by bidirectional edge (\emph{full graph}). In an initially unweighted \emph{full graph} it is possible to assume that shortest paths between any two vertices will contain just single edge (the edge connecting them). In this case all of the \emph{arc-short} circuits will be \(K_3\) graphs.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=150px]{full4}
\caption{option \emph{-d} output: \emph{full4.in}}
\label{full4in}
\end{center}
\end{figure}

\begin{verbatim}
arc-short circuits and bidirectional edges:
[([0, 1]: 2.0), ([0, 2]: 2.0), ([0, 3]: 2.0), ([1, 2]: 2.0), 
([1, 3]: 2.0), ([2, 3]: 2.0), ([0, 1, 2]: 3.0), ([0, 1, 3]: 3.0), 
([0, 2, 1]: 3.0), ([0, 2, 3]: 3.0), ([0, 3, 1]: 3.0), 
([0, 3, 2]: 3.0), ([1, 2, 3]: 3.0), ([1, 3, 2]: 3.0)]
Size: 14, weights sum: 36.000000

min circuit base:
[([0, 1]: 2.0), ([0, 2]: 2.0), ([0, 3]: 2.0), ([1, 2]: 2.0), 
([1, 3]: 2.0), ([2, 3]: 2.0), ([0, 1, 2]: 3.0), ([0, 1, 3]: 3.0), 
([0, 2, 3]: 3.0)]
Size: 9, weights sum: 21.000000

|.|-relevant circuits:
[([0, 1]: 2.0), ([0, 2]: 2.0), ([0, 3]: 2.0), ([1, 2]: 2.0), 
([1, 3]: 2.0), ([2, 3]: 2.0), ([0, 1, 2]: 3.0), ([0, 1, 3]: 3.0), 
([0, 2, 1]: 3.0), ([0, 2, 3]: 3.0), ([0, 3, 1]: 3.0), 
([0, 3, 2]: 3.0), ([1, 2, 3]: 3.0), ([1, 3, 2]: 3.0)]
Size: 14, weights sum: 36.000000
\end{verbatim}

\subsection{\emph{tree5.in}}
This test file contains a digraph with no circuits and bidirectional edges that is \emph{strongly connected} (a \emph{tree graph}). It is designed to test the ability of a program to cope with the lack of possibility to build any \emph{arc-short} circuits. 

\begin{figure}[htb]
\begin{center}
\includegraphics[width=150px]{tree5}
\caption{option \emph{-d} output: \emph{tree5.in}}
\label{tree5in}
\end{center}
\end{figure}

\begin{verbatim}
arc-short circuits and bidirectional edges:
[([0, 1]: 2.0), ([0, 2]: 2.0), ([1, 3]: 2.0), ([1, 4]: 2.0)]
Size: 4, weights sum: 8.000000

min circuit base:
[([0, 1]: 2.0), ([0, 2]: 2.0), ([1, 3]: 2.0), ([1, 4]: 2.0)]
Size: 4, weights sum: 8.000000

|.|-relevant circuits:
[([0, 1]: 2.0), ([0, 2]: 2.0), ([1, 3]: 2.0), ([1, 4]: 2.0)]
Size: 4, weights sum: 8.000000
\end{verbatim}

\subsection{\emph{strcon8.in}} 
This test case shows the correct building of a complete minimum circuit basis (all edges that are part of a circuit colored red).

\begin{figure}[htb]
\begin{center}
\includegraphics[width=150px]{strcon8}
\caption{option \emph{-d} output: \emph{strcon8.in}}
\label{strcon8in}
\end{center}
\end{figure}

\begin{verbatim}
arc-short circuits and bidirectional edges:
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), 
([1, 2, 3]: 3.0), ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), 
([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0), ([0, 6, 4, 2]: 4.0), 
([1, 7, 5, 3]: 4.0), ([0, 6, 7, 5, 3, 4, 2]: 7.0), 
([4, 2, 3, 1, 7, 5, 6]: 7.0)]
Size: 12, weights sum: 46.000000

min circuit base:
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), 
([1, 2, 3]: 3.0), ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), 
([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0), ([0, 6, 4, 2]: 4.0), 
([0, 6, 7, 5, 3, 4, 2]: 7.0)]
Size: 10, weights sum: 35.000000

|.|-relevant circuits:
[([0, 1, 2]: 3.0), ([0, 1, 7]: 3.0), ([0, 6, 7]: 3.0), 
([1, 2, 3]: 3.0), ([2, 3, 4]: 3.0), ([3, 4, 5]: 3.0), 
([4, 5, 6]: 3.0), ([5, 6, 7]: 3.0), ([0, 6, 4, 2]: 4.0), 
([1, 7, 5, 3]: 4.0), ([0, 6, 7, 5, 3, 4, 2]: 7.0)]
Size: 11, weights sum: 39.000000
\end{verbatim}

\subsection{\emph{bidir6.in}}
This graph illustrates test case in which all the edges that are part of a circuit (of a basis) are colored red, while the simple \emph{subtree} \(\{3,4,5\}\) with one vertice \(\{3\}\) in common with the rest of the graph remains blue (it is not part of circuit basis). This graph is not strongly connected.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=150px]{bidir6}
\caption{option \emph{-d} output: \emph{bidir6.in}}
\label{bidir6in}
\end{center}
\end{figure}

\begin{verbatim}
arc-short circuits and bidirectional edges:
[([0, 1]: 2.0), ([0, 3]: 2.0), ([1, 2]: 2.0), ([2, 3]: 2.0), 
([0, 1, 2, 3]: 4.0), ([0, 3, 2, 1]: 4.0)]
Size: 6, weights sum: 16.000000

min circuit base:
[([0, 1]: 2.0), ([0, 3]: 2.0), ([1, 2]: 2.0), ([2, 3]: 2.0), 
([0, 1, 2, 3]: 4.0)]
Size: 5, weights sum: 12.000000

|.|-relevant circuits:
[([0, 1]: 2.0), ([0, 3]: 2.0), ([1, 2]: 2.0), ([2, 3]: 2.0), 
([0, 1, 2, 3]: 4.0), ([0, 3, 2, 1]: 4.0)]
Size: 6, weights sum: 16.000000
\end{verbatim}

\subsection{\emph{EvaluationExample01.in}}
This is the graph proposed as an algorithm evaluation example. It illustrates the unintuitive yet correct minimal base that contains circuit \(\{0, 1, 2, 4, 3, 5\}\) even though all edges where already covered by previously chosen circuits (this circuit is still not a linear combination of shorter circuits).

\begin{figure}[htb]
\begin{center}
\includegraphics[width=150px]{EvaluationExample01}
\caption{option \emph{-d} output: \emph{EvaluationExample01.in}}
\label{EvaluationExample01}
\end{center}
\end{figure}

\begin{verbatim}
arc-short circuits and bidirectional edges:
[([0, 5]: 2.0), ([0, 1, 2]: 3.0), ([3, 5, 4]: 3.0), 
([1, 2, 4, 3]: 4.0), ([0, 1, 2, 4, 3, 5]: 6.0), 
([2, 0, 5, 4, 3, 1]: 6.0)]
Size: 6, weights sum: 24.000000

min circuit base:
[([0, 5]: 2.0), ([0, 1, 2]: 3.0), ([3, 5, 4]: 3.0), 
([1, 2, 4, 3]: 4.0), ([0, 1, 2, 4, 3, 5]: 6.0)]
Size: 5, weights sum: 18.000000

|.|-relevant circuits:
[([0, 5]: 2.0), ([0, 1, 2]: 3.0), ([3, 5, 4]: 3.0), 
([1, 2, 4, 3]: 4.0), ([0, 1, 2, 4, 3, 5]: 6.0), 
([2, 0, 5, 4, 3, 1]: 6.0)]
Size: 6, weights sum: 24.000000
\end{verbatim}

